package leetcode;

class TrieNode {
	TrieNode[] next = new TrieNode[26];
	char node;
	boolean isWord;
	public TrieNode() {
	}
	public void setNode(char c){
		this.node = c;
	}
}

public class Trie {
	private final static int offset = 97;
	private TrieNode root;

	public Trie() {
		root = new TrieNode();
	}

	// Inserts a word into the trie.
	public void insert(String word) {
		char[] cs = word.toCharArray();
		TrieNode current = root;
		for(int i=0;i<cs.length;i++){
			if(current.next[cs[i]-offset]==null){
				current.next[cs[i]-offset] = new TrieNode();
				current = current.next[cs[i]-offset];
				current.node = cs[i];
			} else{
				current = current.next[cs[i]-offset];
			}
		}
		current.isWord = true;
	}

	// Returns if the word is in the trie.
	public boolean search(String word) {
		char[] cs = word.toCharArray();
		TrieNode current = root;
		for(int i=0;i<cs.length;i++){
			if(current.next[cs[i]-offset]==null){
				return false;
			} else{
				current = current.next[cs[i]-offset];
			}
		}
		
		return current.isWord;
	}

	// Returns if there is any word in the trie
	// that starts with the given prefix.
	public boolean startsWith(String prefix) {
		char[] cs = prefix.toCharArray();
		TrieNode current = root;
		for(int i=0;i<cs.length;i++){
			if(current.next[cs[i]-offset]==null){
				return false;
			} else{
				current = current.next[cs[i]-offset];
			}
		}
		return true;
	}
	
	public static void main(String[] args){
		Trie trie = new Trie();
		trie.insert("some");
		trie.insert("someothers");
		trie.insert("dictionary");
		System.out.println(trie.search("someothers"));
		System.out.println(trie.startsWith("some"));
		System.out.println(trie.startsWith("s"));
	}
}


// Your Trie object will be instantiated and called as such:
// Trie trie = new Trie();
// trie.insert("somestring");
// trie.search("key");
